package net.avh4.math;

import java.util.ArrayList;

/**
 * Represents a 2-dimensional array of objects.  The array can be extended infinitely in any direction.
 * <p>
 * NOTE: The current implementation can only be extended to the maximum/minimum values of int.
 *  
 * @author vonderha
 *
 * @param <T>
 */
public class QuadTreeArray<T> {

	/**
	 * Represents the lowest level of the quad tree.  This is a square grid of objects.
	 * @author vonderha
	 *
	 * @param <T>
	 */
	private static class Grid<T> implements QuadTreeArrayIFace<T> {
		private final ArrayList<T> values;
		private final int dimension;
		
		public Grid(final int dimension) {
			this.dimension = dimension;
			values = new ArrayList<T>(dimension*dimension);
			for (int i = 0; i < dimension*dimension; i++) {
				values.add(null);
			}
		}
		
		public T get(int x, int y) {
			assert x >= 0;
			assert y >= 0;
			assert x < dimension;
			assert y < dimension;
			return values.get(x * dimension + y);
		}
		
		public void set(int x, int y, T value) {
			assert x >= 0;
			assert y >= 0;
			assert x < dimension;
			assert y < dimension;
			values.set(x * dimension + y, value);
		}
	}
	
	private static class Quad<T> implements QuadTreeArrayIFace<T> {
		private static final int THRESHOLD = 8;
		
		private final ArrayList<QuadTreeArrayIFace<T>> quads;
		private final int size;
		
		protected Quad(int size) {
			this.size = size;
			quads = new ArrayList<QuadTreeArrayIFace<T>>(4);
			quads.add(null);
			quads.add(null);
			quads.add(null);
			quads.add(null);
		}
		
		public T get(int x, int y) {
			int quad = getIndex(x, y);
			if (quads.get(quad) == null) return null;
			int innerX;
			int innerY;
			if (quads.get(quad) instanceof Grid) {
				innerX = x + ((x < 0) ? size : 0);
				innerY = y + ((y < 0) ? size : 0);
			} else {
				innerX = x + ((x < 0) ? size : 0) - size/2;
				innerY = y + ((y < 0) ? size : 0) - size/2;
			}
			return quads.get(quad).get(innerX, innerY);
		}
		
		public void set(final int x, final int y, final T value) {
			int quad = getIndex(x, y);
			if (quads.get(quad) == null) {
				if (size <= THRESHOLD) {
					quads.set(quad, new Grid<T>(size));
				} else {
					quads.set(quad, new Quad<T>(size/2));
				}
			}
			int innerX;
			int innerY;
			if (quads.get(quad) instanceof Grid) {
				innerX = x + ((x < 0) ? size : 0);
				innerY = y + ((y < 0) ? size : 0);
			} else {
				innerX = x + ((x < 0) ? size : 0) - size/2;
				innerY = y + ((y < 0) ? size : 0) - size/2;
			}
			quads.get(quad).set(innerX, innerY, value);
		}
		
		/**
		 * Returns the index into <code>quads</code> that corresponds to
		 * the given X and Y values.  NOTE: only the sign of X and Y is
		 * relevant to the calculation.
		 * @param signX
		 * @param signY
		 * @return
		 */
		private static int getIndex(int signX, int signY) {
			int quad = ((signX < 0) ? 1 : 0) + ((signY < 0) ? 2 : 0);
			assert quad  >= 0;
			assert quad < 4;
			return quad;
		}
		
		/**
		 * Constructs a new Quad twice as large as <code>oldQuad</code> which
		 * contains the grids of <code>oldQuad</code> at its center.
		 * 
		 *       xx|xx
		 * 12 => x1|2x
		 * 34 => --+--
		 *    => x3|4x
		 *       xx|xx
		 * 
		 * 
		 * @param oldQuad
		 * @return
		 */
		protected static <T> Quad<T> superQuad(Quad<T> oldQuad) {
			Quad<T> superQuad = new Quad<T>(oldQuad.size * 2);
			for (int i = 0; i < 4; i++) {
				superQuad.quads.set(i, new Quad<T>(oldQuad.size));
			}
			((Quad<T>)superQuad.quads.get(getIndex(-1,-1))).quads.set(getIndex(+1,+1), oldQuad.quads.get(getIndex(-1,-1)));
			((Quad<T>)superQuad.quads.get(getIndex(-1,+1))).quads.set(getIndex(+1,-1), oldQuad.quads.get(getIndex(-1,+1)));
			((Quad<T>)superQuad.quads.get(getIndex(+1,-1))).quads.set(getIndex(-1,+1), oldQuad.quads.get(getIndex(+1,-1)));
			((Quad<T>)superQuad.quads.get(getIndex(+1,+1))).quads.set(getIndex(-1,-1), oldQuad.quads.get(getIndex(+1,+1)));
			return superQuad;
		}
	}
	
	private interface QuadTreeArrayIFace<T> {
		public void set(final int x, final int y, final T value);
		public T get(final int x, final int y);
	}
	
	private Quad<T> root;
	private int size;
	
	public QuadTreeArray() {
		this(8);
	}
	
	public QuadTreeArray(int gridSize) {
		this.size = gridSize;
		root = new Quad<T>(size);
	}
	
	public void set(int x, int y, T value) {
		while (x >= size || y >= size || x < -size || y < -size) {
			splitQuad(); 
		}
			
		root.set(x, y, value);
	}
	
	public T get(int x, int y) {
		if (x >= size || y >= size || x < -size || y < -size) {
			return null; 
		}
		return root.get(x, y);
	}
	
	private void splitQuad() {
		size = size * 2;
		Quad<T> newRoot = Quad.superQuad(root);
		root  = newRoot;
	}
}
